Motion compensation is a widely employed evolving video image processing technology. Areas of application include image compression, transcoding, de-interlacing and frame rate conversion of video data. Motion estimation forms an integral and core component of any motion compensation method.
The goal of motion estimation is to estimate the motion of every pixel in a frame of video data under consideration (‘current frame’), relative to pixels in other frame(s), in a sequence of video frames. In essence, motion estimation assigns to every pixel, motion information in the form of motion vectors (representing the motion in two dimensions i.e. horizontal and vertical) linked to other frame(s).
Many techniques and algorithms exist to obtain motion vectors, of which, block-matching based methods form a commonly-used subset. The basic principle of block-matching is to find a block (i.e., a group of pixels aligned in some pre-determined fashion e.g. rectangular, triangular, diamond-shaped shaped blocks) of data in the previous or any other frame which best matches the block under consideration in the current frame. The “best match” is decided in terms of a chosen metric such as mean-squared error (MSE), mean-absolute error (MAE), peak signal to noise ratio (PSNR), sum of squared errors (SSE), sum of absolute difference (SAD), etc. All pixels comprising the block under consideration in the current frame have the same motion vector.
Various other techniques such as optical flow also exist which determine the motion vector for a pixel or block, based on error metrics. FIGS. 1-4 show conventional approaches described below.
FIG. 1 illustrates a method of block-matching based motion estimation. If Bx,yt represents a block at location (x, y) in the current frame It of size m×n pixels, and Bx+dx,y+dyt−1 represents a block displaced from location (x, y) by (dx, dy) in the previous frame It−1 (also of size m×n pixels), then the SAD between the two blocks for the motion vector (dx, dy) is given by the expression (1):
                              SAD          ⁡                      (                          dx              ,              dy                        )                          =                              ∑                          i              =              0                                      m              -              1                                ⁢                                    ∑                              j                =                0                                            n                -                1                                      ⁢                                                                                              B                                          x                      ,                      y                                        t                                    ⁡                                      (                                          i                      ,                      j                                        )                                                  -                                                      B                                                                  x                        +                        dx                                            ,                                              y                        +                        dy                                                                                                                                                        ⁢                                              t                        -                        1                                                                              ⁡                                      (                                          i                      ,                      j                                        )                                                                                                                        (        1        )            
where Bx, yt(i, j) represents pixel (i, j) within the block (with this representation, location (0, 0) within the block refers to the block starting position of (x, y)).
One of the problems encountered in the process of motion estimation is the determination of the reliability of the computed motion vector. Intuitively, it appears that smaller values of the SAD represent better matches and hence more accurate motion vectors while large values of the SAD represent poor matches and consequently inaccurate motion vectors. Accordingly, the best motion vector (vx, vy) is the one that minimizes the SAD metric over all possible motion vectors. Typically, a subset of all possible motion vectors (defined by a search area and search resolution), denoted by Δ, is used. Mathematically by expression (2):SAD(vx, vy)≦SAD(dx, dy), where (dx, dy) εΔ⊂2  (2)
where SAD(dx, dy) is computed as mentioned in expression (1). However, in practice, the range of SAD values for reliable matches shows much variation with content.
The example in FIG. 2 shows the SAD surface and lists the minimum SAD value and the corresponding motion vector for one block in a test video sequence for the case when the estimated motion vector represents the true motion. The example in FIG. 3 shows another example where the motion vector was correctly estimated. FIG. 4, on the other hand, shows an example of an unreliable motion vector due to multiple object motion within the block.
As can be seen from FIGS. 2-4, the SAD value alone does not provide any indication of the reliability of the estimated motion vector. Factors such as noise, dynamic range, high-frequency information, multiple objects with differing motion, and various others, affect the range of SAD values that can be termed as reliable matches. The use of incorrect motion vectors has detrimental effects in any application relying on motion estimation or compensation. For example, in compression systems, the use of incorrect motion vectors leads to lower output video quality for a given bit rate; in frame rate conversion and de-interlacing applications, the use of incorrect motion vectors for motion compensation results in visual artifacts in the output video. Thus, the determination of the reliability of the estimated motion vector plays a crucial role in obtaining high quality output video.